package com.lx.algorithm.temp;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-26 14:44:33
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-26     张李鑫                     1.0         1.0 Version
 */
public class ConvertToLetterString {
    /**
     * 规定1和A对应、2和B对应、3和C对应...26和Z对应
     * 那么一个数字字符串比如"111”就可以转化为:
     * "AAA"、"KA"和"AK"
     * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
     */

    public static void main(String[] args) {
        int N = 30;
        int testTime = 1000000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * N);
            String s = randomString(len);
            int ans0 = process(s.toCharArray());
            int ans2 = programming(s.toCharArray());
            if (ans0 != ans2) {
                System.out.println(ans0);
                System.out.println(ans2);
                System.out.println("Oops!");
                break;
            }
        }
        System.out.println("测试结束");
    }

    // 为了测试
    public static String randomString(int len) {
        char[] str = new char[len];
        for (int i = 0; i < len; i++) {
            str[i] = (char) ((int) (Math.random() * 10) + '0');
        }
        return String.valueOf(str);
    }
    public static int process(char[]chars){
        if (chars == null || chars.length == 0) {
            return 0;
        }
        return process(chars,0);
    }


    public static int process(char[] str, int i) {
        if (i == str.length) {
            return 1;
        }
        if (str[i] == '0') {
            return 0;
        }
        int ways = process(str, i + 1);
        if (i + 1 < str.length && (str[i] - '0') * 10 + str[i + 1] - '0' < 27) {
            ways += process(str, i + 2);
        }
        return ways;
    }


    public static int programming(char[] chars) {
        if (chars == null || chars.length == 0) {
            return 0;
        }
        int[] arr = new int[chars.length + 1];
        arr[chars.length] = 1;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] != '0') {
                int count=arr[i+1];
                if (i + 1 < chars.length && (chars[i] - '0') * 10 + chars[i + 1] - '0' < 27) {
                    count += arr[i+2];
                }
                arr[i]=count;
            }
        }
        return arr[0];
    }
}

